package LimitedTimeGame.Day_0214;

/**
 * @author zxc
 * @date 2023/02/14 11:04
 **/

import java.util.Arrays;

/**
 * 题目 ：表现良好的最长时间段
 * 题目详述 ：
 * 给你一份工作时间表hours，上面记录着某一位员工每天的工作小时数。
 * 我们认为当员工一天中的工作小时数大于8 小时的时候，那么这一天就是「劳累的一天」。
 * 所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
 * 请你返回「表现良好时间段」的最大长度。
 *
 * 提示：
 * 1 <= hours.length <= 104
 * 0 <= hours[i] <= 16
 *
 */
public class LongestWPI {
    public static void main(String[] args) {
        System.out.println(longestWPI(new int[]{6, 6, 9}));
    }
    /**
     * 思路 ：
     * int len = hours.length();
     * ===> 即，遍历长度从len ~ 1的所有可能情况
     * ===》导致超时，时间复杂度O(n ^ 3)
     * @param hours
     * @return
     */
    public static int longestWPI(int[] hours) {
        int len = hours.length;
        int result = 0;
        for(int i = 0 ; i < len ; i++){
            for(int j = len - 1 ; j >= i ; j--){
                if(isWellHours(i , j , hours)){
                    result = Math.max(result , j - i + 1);
                }
            }
        }
        return result;
    }

    private static boolean isWellHours(int i, int j, int[] hours) {
        int[] dp = new int[j - i + 1];
        for(int k = i,l = 0; k <= j ; k++,l++){
            dp[l] = hours[k];
        }
        Arrays.sort(dp);
        int len = dp.length;
        if(dp[(len - 1) / 2 ] > 8){
            return true;
        }
        return false;
    }
}
